from collections import deque
from typing import Optional, List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        self.res = 0
        self.depth = 0
        self.traverse(root)
        return self.res

    def traverse(self, root: Optional[TreeNode]):
        if root is None:
            return
        self.depth += 1
        if root.left is None and root.right is None:
            self.res = max(self.depth, self.res)
        self.traverse(root.left)
        self.traverse(root.right)
        self.depth -= 1


    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0
        self.traverseForDiameter(root)
        return self.diameter

    def traverseForDiameter(self, root: Optional[TreeNode]):
        if root is None:
            return 0
        leftDiameter = self.traverseForDiameter(root.left)
        rightDiameter = self.traverseForDiameter(root.right)
        self.diameter = max(leftDiameter + rightDiameter, self.diameter)
        return max(leftDiameter, rightDiameter) + 1

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return root
        temp = root.left
        root.left = root.right
        root.right = temp
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root

        queue = deque([root])

        while queue:
            size = len(queue)
            for i in range(size):
                top = queue.popleft()
                if i < size - 1:
                    top.next = queue[0]

                if top.left:
                    queue.append(top.left)

                if top.right:
                    queue.append(top.right)

        return root

    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root is None:
            return
        self.tempList: Optional[List[TreeNode]] = []
        self.traverseForFlatten(root)
        for i in range(len(self.tempList) - 1):
            self.tempList[i].left = None
            self.tempList[i].right = self.tempList[i + 1]

    def traverseForFlatten(self, root):
        if root is None:
            return
        self.tempList.append(root)
        self.traverseForFlatten(root.left)
        self.traverseForFlatten(root.right)


    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        return self.construct(nums, 0, len(nums) - 1)

    def construct(self, nums, low, high):
        if low > high:
            return None
        maxIndex = low
        for i in range(low + 1, high + 1):
            if nums[i] > nums[maxIndex]:
                maxIndex = i

        root = TreeNode(nums[maxIndex])
        root.left = self.construct(nums, low, maxIndex - 1)
        root.right = self.construct(nums, maxIndex + 1, high)
        return root


    def buildTreeByPreAndIn(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        size = len(preorder)
        root = TreeNode(preorder[0])
        stack = [root]
        inorderIndex = 0
        for i in range(1, size):
            preorderVal = preorder[i]
            node = stack[-1]
            if node.val != inorder[inorderIndex]:
                node.left = TreeNode(preorderVal)
                stack.append(node.left)
            else:
                while stack and stack[-1].val == inorder[inorderIndex]:
                    node = stack[-1]
                    stack.pop()
                    inorderIndex += 1

                node.right = TreeNode(preorderVal)
                stack.append(node.right)

        return root

    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        size = len(postorder)
        root = TreeNode(postorder[-1])
        stack = [root]
        inorderIndex = size - 1
        for i in range(size - 2, -1, -1):
            postorderVal = postorder[i]
            node = stack[-1]
            if node.val != inorder[inorderIndex]:
                node.right = TreeNode(postorderVal)
                stack.append(node.right)
            else:
                while stack and stack[-1].val == inorder[inorderIndex]:
                    node = stack[-1]
                    stack.pop()
                    inorderIndex -= 1

                node.left = TreeNode(postorderVal)
                stack.append(node.left)

        return root

    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        size = len(preorder)
        map = {x: i for i, x in enumerate(postorder)}

        def dfs(preLeft, preRight, postLeft, postRight):
            if preLeft > preRight:
                return None

            leftCount = 0
            if preLeft < preRight:
                leftCount = map[preorder[preLeft + 1]] - postLeft + 1

            return TreeNode(preorder[preLeft],
                            dfs(preLeft + 1, preLeft + leftCount, postLeft, postLeft + leftCount - 1),
                            dfs(preLeft + leftCount + 1, preRight, postLeft + leftCount, postRight - 1))

        return dfs(0, size - 1, 0, size - 1)

    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        def dfs(node: Optional[TreeNode]) -> str:
            if not node:
                return ""
            serial = "".join([str(node.val), "(", dfs(node.left), ")(", dfs(node.right), ")"])
            # 在Python3.8及更高版本中，引入了一种新的语法特性，称为"海象运算符"（Walrus Operator），它使用 := 符号。这个运算符的主要目的是在表达式中同时进行赋值和返回赋值的值。
            # Return the value for key if key is in the dictionary, else default.
            if (tree := seen.get(serial, None)):
                repeat.add(tree)
            else:
                seen[serial] = node
            return serial

        seen = dict()
        repeat = set()
        dfs(root)
        return list(repeat)


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        self.res = ""

        def rSerialize(root: Optional[TreeNode]):
            if root is None:
                self.res += "None,"
            else:
                self.res += str(root.val) + ','
                rSerialize(root.left)
                rSerialize(root.right)

        rSerialize(root)
        return self.res

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        list = deque([x for x in data.split(',') if x])

        def rDeserialize():
            if list[0] == "None":
                list.popleft()
                return None
            root = TreeNode(int(list.popleft()))
            root.left = rDeserialize()
            root.right = rDeserialize()
            return root

        return rDeserialize()



if __name__ == '__main__':
    # root = TreeNode(1)
    # root.left = TreeNode(2)
    # root.right = TreeNode(5)
    # root.left.left = TreeNode(3)
    # root.left.right = TreeNode(4)
    # root.right.right = TreeNode(6)
    solution = Solution()
    # solution.flatten(root)
    root = solution.buildTree([3,9,20,15,7], [9,3,15,20,7])
    print(root)
    print("123,456,".split(','))
    print([x for x in "123,456,".split(',') if x])